1. Field of the Invention
The present invention relates to the field of computer systems, in particular, data retrieval techniques in computer systems. More specifically, the present invention relates to data retrieval from a physically addressed data storage structure, e.g. a physically addressed set associative instruction cache.
2. Background
In order to expedite the availability of data and improve the overall system performance, there are many situations where a plurality of data vectors and their corresponding selection vectors are stored in an organized manner in complementary storage structures. A data vector is a collection of multiple data blocks, where each data block is in turn a collection of multiple data elements. A selection vector is a collection of corresponding selection elements. Such storage structures may be found in many general as well as special purpose computers regardless of their architectures. Perhaps the most well known example of such storage structures is a set associative cache. Another example is a multi-bank memory system. A not as well known example is a branch prediction table.
Additionally, to further expedite the availability of data and improve the overall system performance, many systems that support virtual addressing have taken the approach of accessing these storage structures with virtual addresses. Such an approach has the advantage of not having to wait for the virtual addresses to be translated into physical addresses. However, as the number of virtual address spaces supported increases, experience has shown that the overhead incurred during address space switching begins to outweigh the benefits of accessing these storage structures with virtual addressing. Thus, some virtual addressing systems that support large number of virtual address spaces have switched back to accessing these storage structures with physical addresses. Of course, the disadvantage is that the accesses cannot be completed until the virtual addresses are translated.
However, for storage structures whose sizes are larger than the memory page sizes of the systems and having a "sequential" access tendency, the translated portions of the accessing physical addresses tend to remain unchanged between successive accesses. Thus, it is desirable to exploit these characteristics and improve the performance of retrieving data from these storage structures. As will be disclosed, the present invention provides a method and apparatus for rapidly retrieving data from physically addressed data storage structures using memory page crossing predictive annotations, which achieves the objects and desired results described earlier by exploiting these characteristics.